\chapter{Formalizácia reprezentácie rozhodovacích procesov}

V tejto kapitole sa zoznámime so základnými teoretickými vedomosťami, ktoré
nám poslúžia v ďalších kapitolách, v ktorých na nich postavíme už konkrétne
implementácie rozhodovacích procesov v CDSS systémoch. Zoznámime sa
s oblasťami:
\begin{itemize}
\item teória množín,
\item predikátová logika,
\item deskripčná logika,
\item a maticový počet.
\end{itemize}

Základné znalosti z teórie množín sú potrebné pre štúdium akýchkoľvek
metód, ktoré sú -- ako v našom prípade -- vystavané na matematických
základoch. Predikátovú a deskripčnú logiku využijeme pri štúdiu znalostných
metód v kapitole~\ref{chap:analyza}. Maticový počet zasa potrebujeme pri
niektorých aplikáciách dolovania znalostí v kapitole~\ref{chap:dolovanie}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Teória množín}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Teória množín je jedna zo základných a zároveň kľúčových oblastí
matematiky. Táto oblasť matematiky skúma vlastnosti množín, vzájomné vzťahy
medzi množinami, operácie s množinami, ich mohutnosť, a ich ďalšie vlastnosti.
V tejto časti sa s teóriou množín stručne zoznámime, aby sme vybudovali
potrebný základ pre ďalšie časti. Viac čitateľ nájde v \cite{beton}.

Na to, aby sme vedeli pracovať s množinami je potrebné zadefinovať si jednotlivé pojmy.

\begin{definition}
\textbf{Množina}

Množina je dobre definovaný súbor (zbierka) rôznych prvkov (objektov). Množiny označujeme
veľkými písmenami 
$M,S,P, \ldots $ a objekty (prvky) množiny označujeme malými písmenami latinskej abecedy
$M = {a, b, c, d} $.
\end{definition}

Prvkami množiny môže byť čokoľvek: farba, čísla, zvieratá. Pre naše potreby uvažujme množinu symptómov chrípky $S$.

$$ S = \{kašeľ, bolesť\ hrdla, plný\ nos, bolesť\ hlavy, horúčka, zimnica, dehydratácia\}$$ 

Je dôležité si všimnúť, že každý jeden z týchto symptómov je pre množinu
$S$ unikátny. Unikátny znamená, že každý jeden prvok je jedinečný, čiže sa
odlišuje od ostatných.

\begin{definition}
\textbf{Podmnožina}

Ak A a B sú množiny a zároveň každý prvok množiny A je aj prvkom množiny B potom
\begin{itemize}
\item
A je podmnožinou množiny B, označujeme $A \subseteq B$
\end{itemize}

Ak A je podmnožinou B a zároveň existuje aspoň jeden prvok z B, ktorý sa nenachádza v A potom
\begin{itemize}
\item
A je ostrou podmnožinou množiny B, označujeme $A\subset B$
\end{itemize}
\end{definition}

Inak povedané podmnožina množiny obsahuje iba prvky z danej množiny a
väčšinou menší počet prvkov ako je daná množina. Príkladom môže byť napríklad množina zriedkavých príznakov chrípky $S_{Z}$ medzi ktoré môžeme zaradiť napríklad zimnicu, alebo dehydratáciu.

$$S_{Z} = \{zimnica, dehydratácia, horúčka \}$$ 

Do ďalšej podmnožiny s názvom časté príznaky chrípky zaradíme napríklad bolesť hrdla a plný nos 

$$S_{C} = \{ bolesť\ hrdla, plný\ nos \}$$ 

Potom dostaneme:  
	
$$S_{C} \subseteq S$$ 
	
$$S_{Z} \subseteq S$$ 

\begin{definition}
\textbf{Kardinalita}

Kardinalitou alebo mohutnosťou množiny označuje veľkosť množiny, čiže počet
prvkov množiny. 
\end{definition}

Pre naše príklady uvedené vyššie dostaneme potom: 

$$\mid S \mid = 7$$ 

$$\mid S_{Z} \mid  =  3$$ 

$$\mid S_{C} \mid = 2$$ 

\textbf{Operácie na množinách}

Ďalej sa oboznámime s rôznymi operáciami na množinách. 
Základné operácie na množinách sú zjednotenie a prienik. 
Je treba si uvedomiť, že výsledkom operácie na množine je zase množina a taktiež aj prázdna množina je množina. 

\begin{definition}
\textbf{Zjednotie dvoch množín}

Zjednotenie dvoch množín A a B je taká množina, pre ktorú platí:

$$x \in A \cup B \Longleftrightarrow ( x \in A \vee x \in B )$$
\end{definition}

Zjednotenie dvoch množín je teda taká množina, ktorá obsahuje všetky prvky,
ktoré sa nachádzajú aspoň v jednej zo zjednocovacích množín. 
Nezabúdajme však, že prvky množiny sú unikátne, to znamená, že ak sa nejaký prvok nachádza aj v množine prvej aj v druhej, vo výslednej množine sa bude prvok nachádzať iba raz.

Môžeme si uviesť príklad: 

Keď zjednotíme zriedkavé a časté príznaky chrípky dostaneme naspať celú
množinu symptómov chrípky, čiže dostaneme rovnosť.

$$S_{Z} \cup S_{C}  = S$$

\begin{definition}
\textbf{Prienik dvoch množín}

Prienik dvoch množín A a B je taká množina, pre ktorú platí:

$$x \in A \cap B \Longleftrightarrow ( x \in A \wedge x \in B )$$ 
\end{definition}

Inými slovami prienik dvoch množín je taká množina, ktorá obsahuje prvky spoločné pre tieto dve množiny. 

Napríklad máme pacienta s nasledovnými príznakmi:

$$P = \{  bolesť\ hrdla, bolesť\ hlavy, bolesť\ kĺbov \}$$ 

Potom prienikom množiny symptómov chrípky $S$ a množiny príznakov u pacienta $P$ dostaneme množinu

$$P \cap  S  = \{ bolesť\ hrdla, bolesť\ hlavy \}$$

Mohutnosť vieme využiť aj v tomto smere. Napríklad aj takto\\

	$$\mid S \sqcap P \mid \geq 2$$


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Matematická logika}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Matematická logika vznikla za účelom formalizovať usudzovanie. Preto je logika dobrým nástrojom na prácu so znalosťami. Je potrebné aby sme vedeli znalosti správne reprezentovať. Znalostné systémy musia znalosti reprezentovať v nejakom jazyku. 
Kedy je usudzovanie správne a kedy naopak nesprávne? Matematická logika sa
zaoberá práve takýmito schémami, kedy je usudzovanie správne (korektné)
nezávisle od pravdivosti či nepravdivosti jeho zložiek.

Na reprezentovanie znalostí potrebujeme formálny jazyk. Formálny jazyk je
taký jazyk, ktorý je presne stanovený a o každej vete vieme povedať či do
jazyka patrí alebo nie. Každá veta v tomto jazyku má svoj presný význam.
Jeden z takýchto jazykov je Predikátová logika prvého rádu (FOL, z
anglického \emph{First Order Logic}). Častejšie sa hovorí iba predikátová
logika. Je logika, ktorá na rozdiel od výrokovej logiky
obsahuje kvantifikované premenné, takzvané kvantifikátory.
V tejto časti sa
stručne stručne zoznámime s jazykom FOL, s jeho sémantikou, ako aj s pojomo
dôkazu. Viac informácií čitateľ nájde v \cite{logika}.


Rozlišujeme dva druhy znalostí -- znalosti, ktoré poznáme, máme na začiatku dané a znalosti, ktoré vieme odvodiť.
Znalosti, ktoré poznáme nazývame znalosti explicitné a tie, ktoré odvodzujeme sú znalosťami implicitnými. Práve logika nám umožňuje vyvodzovať z explicitných znalostí tie implicitné, ktoré nemáme priamo dané, ale vieme ich odvodiť.

Aby sme si to vedeli lepšie predstaviť výroková logika sa zaoberá výrokmi a ich pravdivostnými hodnotami. Výroková logika však nepokrýva všetky situácie a možnosti ľudského 
usudzovania, ktoré sú podstatne  bohatšie, ako možnosti výrokovej 
logiky. Ohraničenosť výrokovej logiky je možné prekonať jej 
zovšeobecnením na predikátovú logiku, ktorá je schopná postihnúť aj 
procesy usudzovania. V predikátovej logike pracujeme s predikátmi a
kvantifikátormi. Predikáty si môžeme predstaviť ako boolovské funkcie,
ktoré nadobúdajú hodnotu \emph{True} alebo \emph{False} (pravda / nepravda).

\subsection{Syntax}

Ďalej sa predikátová logika skladá z dvoch hlavných častí -- \emph{Syntax}
a \emph{Sémantika}.  \emph{Syntax} popisuje aké postupnosti písmen a slov
sú možné a legálne ich môžeme používať v našom jazyku a \emph{Sémantika}
vyjadruje význam jednotlivých výrazov.

Najprv si niečo povieme o syntaxi jazyka predikátovej logiky.  Jazyk
predikátovej logiky tak ako aj jazyk slovenčina sa skladá zo symbolov a
znakov. Hovoríme tomu abeceda jazyka.

\begin{definition}
\textbf{Abeceda}
Abeceda obsahuje

\begin{itemize}
\item
Množina premenných\\
$V = \{x, y, z, \dots\}$
\item
Množina funkčných symbolov\\
$F = \{f, g, h, \dots\}$
\item
Množina predikátov\\
$P = \{p, q, r, \dots\}$
\item
Logické spojky\\
$\neg, \lor, \land, \rightarrow, \leftrightarrow$
\item
Kvantifikátory\\
$\forall \quad \exists$
\item
Pomocné symboly\\
$( \quad ) \quad ,$
\end{itemize}
\end{definition}

Doménu môžeme chápať ako neprázdnu množinu objektov nášho univerza. 
Predikátová logika pracuje nad takzvanou \emph{univerzálnou množinou}, ktorej sa niekedy hovorí aj \emph{Univerzum}. Doména je teda podmnožina univerza.

Aby sme vedeli pracovať s jazykom v abecede sme si zaviedli všetky potrebné
a legálne symboly. Premenné zastupujú objekty nášho \emph{univerza}

Môžeme si uviesť príklad.
Budeme mať dva výroky:

\begin{equation}
  \text{,,Zelená je farba.''}
  \label{eq:zelena}
\end{equation}
\begin{equation}
  \text{,,Modrá je farba.''}
  \label{eq:modra}
\end{equation}

Vo výrokovej logike ide o dva nezávisle výroky. Máme teda dva výroky, výrok
\eqref{eq:zelena} a \eqref{eq:modra}.
V predikátovej logike pracujeme s predikátmi,  čo je v tomto prípade
predikát \emph{Farba}. Potom predikát použitím konštánt \emph{modrá} a
\emph{zelená} bude vyjadrovať presne to isté čo výroky \eqref{eq:zelena} a
\eqref{eq:modra}. Dostaneme teda \emph{Farba(modrá)} a \emph{Farba(zelená)}.

Budeme sa stretávať aj s pojmom ako je arita funkcie. Arita funkcie nám hovorí iba o tom, koľko argumentov (premenných) predikát obsahuje. 

\begin{definition}
\textbf{Arita funkcie} 

Arita funkcie špecifikuje koľko ,,argumentov'' každá funkcia a predikát
si vyžaduje.
Funkcie (predikáty) arity $0$, $1$, $2$, $3$, a tak ďalej sú nazývané:
nulárne, unárne, binárne, ternárne, a tak ďalej.
\end{definition}

Ak zoberieme predikát \emph{L(x)}, jeho arita je 1. Pre predikát \emph{P(x, y, z)} je jeho arita 3 atď.

V predikátovej logike rozlišujeme dva základne druhy výrazov -- \emph{termy} a \emph{formuly}. 

Termy si môžeme predstaviť ako všeobecný pojem pre premenné a funkciu, kde ako argumenty berieme znova iba premenné. Formálnejšie to vieme zapísať nasledovne:

\begin{definition}
\textbf{Term} 

Je daná abeceda a arita funkcie,  \emph{term} je potom jeden z nasledujúcich možností:

\begin{itemize}
\item
premenná;
\item
výraz $f(t_1, \dots, t_n)$ ak $f$ je funkcia s aritou
$n$ a $t_1, \dots, t_n$  sú termy.
\end{itemize}
\end{definition}

\begin{definition}
\textbf{Uzavretý term}

Term $t$ je \emph{uzavretý} ak neobsahuje žiadne premenné
\end{definition}

Konštanty sú tiež dôležité, akurát v našom jazyku ich nepotrebujeme formálne zavádzať
osobitne -- pretože miesto nich rovnako dobre poslúžia nulárne termy tvaru $f()$, kde $f$ je funkčný symbol, pričom v takom prípade zátvorky vynecháme. Čiže,
konštanty sú vlastne len syntaktický cukor.

Zadefinujeme si aj iné pojmy, ktoré existujú a budeme ich potrebovať. 
Jedným z takých pojmov je aj Atomická formula alebo atóm, ktorý sa spomína v definícii formuly.
atóm nie je nič iné ako predikát, ktorý ako argumenty berie na vstupe termy.

\begin{definition}
\textbf{Atóm}

Je daná abeceda a arita funkcie, \emph{atomická formula}
(atóm) je výraz $p(t_1, \dots, t_n)$ kde
$p$ je predikátový symbol s aritou $n$ a $t_1, \dots, t_n$ sú termy.
\end{definition}

\begin{definition}
\textbf{Uzavretý atóm}

Atóm $A$ je \emph{uzavretý atóm} ak neobsahuje žiadnu voľnú premennú.
\end{definition}

Atóm je teda špeciálna formula, ktorá je bez hlbšej výrokovej štruktúry. To znamená formula, ktorá neobsahuje žiadne logické spojky. 

Ako ďalšiu časť logiky si predstavíme formule. Formule sú vety jazyka FOL, ktoré sa skladajú nejakým špecifickým spôsobom z atomických formúl (atómov) a logických spojok. O každej formuli budeme chcieť povedať, či je pravdivá, alebo nie, čo sa dozvieme nižšie pri sémantike.

\begin{definition}
\textbf{Formula}

Je daná abeceda a arita funkcie, \emph{formula} je niektorý výraz
z nasledujúcich možností:
\begin{itemize}
\item
atóm;
\item
$\neg \Phi$;
\item
$(\Phi \land \Psi)$;
\item
$(\Phi \lor \Psi)$;
\item
$(\Phi \rightarrow \Psi)$;
\item
$(\Phi \leftrightarrow \Psi)$;
\item
$(\forall x)\Phi$;
\item
$(\exists x)\Phi$;
\end{itemize}
\medskip kde $\Phi,\Psi$ sú formuly, a $x$ je premenná.
\end{definition}

Ako sme si skôr hovorili ak chceme zapísať či reprezentovať znalosti k tomu potrebujeme jazyk. 

\begin{definition}
\textbf{Jazyk predikátovej logiky}

\emph{Jazyk} prvorádovej logiky (predikátovej logiky) nad nejakou abecedou
a príslušnou funkciou arity je množina $\mathcal{L}$ všetkých formúl.
\end{definition}

Zaviedli sme si základné pojmy na prácu so znalosťami a prácu s nimi.
Všetky znalosti vieme dať a popísať v takzvanej báze znalostí. Báza
znalostí je hocijaká konečná množina formúl nášho jazyka. \\ Takejto báze
sa formálnejšie hovorí aj \emph{Teória}. Teória má
svoj význam. Tie formule pre nás predstavujú popis nejakého stavu sveta,
situácie, problému. Následne sémantika nám umožní zistiť, čo v
takom svete/pre taký problém platí (čiže vyplýva).

\begin{definition}
\textbf{Teória}

Prvorádová teória (alebo len \emph{teória}) $T$ je konečná množina 
formúl nejakého jazyka $\L$.
\end{definition}

Pre lepšie pochopenie si uvedieme príklad. Predpokladajme nasledujúcu
situáciu: \emph{Jack zabil Johna. Ak niekto niekoho zabije, je to vrah.
Vrahovia idú do väzenia.} Môžeme to zakódovať
do FOL teórie $T$:
\begin{gather*}
\mathit{Zabil(Jack,John)}\\
\mathit{(\forall x)((\exists y) Zabil(x,y) \rightarrow Vrah(x))}\\
\mathit{(\forall x) (Vrah(x) \rightarrow Väzenie(x))}
\end{gather*}

V tomto príklade si môžeme všimnúť nasledovné výrazy:

\begin{itemize}
\item
$x, y, z$ -- premenné;
\item
$Jack, John$ -- konštanty;
\item
$Zabil, Väzenie, Vrah$ -- predikáty;
\end{itemize}

\subsection{Sémantika}

Ako sme si na začiatku povedali poznáme dve základné časti logiky -- syntax
a sémantiku.
Doteraz sme sa zaoberali a popisovali syntax prvorádovej logiky nazývanej
aj predikátová logika. Teraz si povieme niečo o sémantike. 

Sémantiku chápeme ako význam jednotlivých syntaktických výrazov alebo inak povedané pravdivostné hodnotenie formúl predikátovej logiky. Treba nám ju v konečnom dôsledku na to, aby sme mohli formálne zadefinovať splniteľnosť a vyplývanie, čo sú jedny zo základných pojmov na prácu so znalosťami. 

Proces pravdivostného hodnotenia formúl predikátovej logiky je 
podstatne zložitejší proces ako vo výrokovej logike. K tomu, aby sme vedeli a mohli tento proces korektne realizovať, musíme poznať takzvanú interpretáciu konštánt 
a predikátových symbolov. Pre lepšie pochopenie si uvedieme ilustračný príklad.

Majme formulu  

$$(\forall x)( P(x) \Rightarrow (\exists y) Q (x, y)) $$

kde P je unárny predikát a Q je 
binárny predikát. Uvažujme tieto dve rôzne interpretácie: 

\begin{itemize}
\item
Interpretácia \emph{I1}. Indivíduá sú ľudia. Predikát P(x) reprezentuje vlastnosť
„objekt  x je učiteľ“ a predikát  Q(x,y) reprezentuje vlastnosť objekt  y je 
žiakom objektu  x. Potom daná formula má význam „každý učiteľ má 
aspoň jedného žiaka, pravdivostná hodnota tejto formuly je pravda;
\item
Interpretácia \emph{I2}. Indivíduá sú prirodzené čísla. Predikát P(x) reprezentuje 
vlastnosť „objekt  x je prvočíslo“, predikát Q(x,y) reprezentuje vlastnosť
„objekt x je deliteľný objektom  y, pričom  y $\neq$ x.  Význam formule je „pre 
každé prvočíslo x existuje také iné prvočíslo y, ktoré je deliteľom x“, čo je 
evidentne  nepravdivý výraz;
\end{itemize}  
  
Z toho jednoduchého príkladu vyplýva, že pravdivostná hodnota predikátovej 
formuly je určená interpretáciou I premenných, konštánt a predikátov. 

Za týmto účelom zadefinujeme pojem model a budeme skúmať či má formula model, čiže či je formula splniteľná a či niečo platí vo všetkých modeloch teórie z čoho sa dostávame ku vyplývaniu. Teda budeme sa pýtať, či existuje model danej teórie a tým pádom či daná formula je splniteľná a nie je to len taký nezmysel. Modely nám teda napomáhajú sa pýtať či ma alebo nemá daná formula zmysel. Ako modely budeme skúmať matematické štruktúry -- ktoré môžu byť modelom, alebo nemusia. 

Štruktúra je dvojica -- Doména a Interpretácia. 

\begin{definition}
\textbf{Štruktúra}

\emph{Štruktúra} je dvojica
$\D = (\Dom, I)$ kde
\begin{itemize}
\item
$D$, nazývaná \emph{doména}, je neprázdna množina;
\item
$I$, nazývaná \emph{interpretácia}, je funkcia kde:
\begin{itemize}
\item
$I(f)$ je funkcia $f^I \colon \Dom^{\mathit{arity}(f)} \to \Dom$;
\item
$I(t)$ je $t^I = f^I(t_1^I,\dots,t_n^I)$ pre hocijaký uzavretý term tvaru $t
= f(t_1,\dots,t_n)$;
\item
$I(p)$ je relácia $p^I \subseteq \Dom^{\mathit{arity}(p)}$.
\end{itemize}
\end{itemize}
\end{definition}

Štruktúra samotná ešte nehovorí o tom, či je formula pravdivá alebo nie. V
niektorých štruktúrach môže byť, a v iných nie. Aby sme to vedeli posúdiť,
potrebujeme si zadefinovať kedy je formula pre danú štruktúru splnená.
Všimnime si však, že v definícii štruktúry sme nikde nepriradili žiadny
význam premenným. Potrebujeme preto ešte jeden pomocný pojem -- špeciálne
štruktúry, ktoré to robia budeme nazývať rozšírenia.

\begin{definition}
\textbf{Rozšírenie štruktúry}

\emph{Rozšírenie štruktúry $\D = (\Dom,I)$ vzhľadom na premennú
$x$} je štruktúra $\D' = (\Dom,I')$, kde interpretácia $I'$ je identická s
$I$, ale navyše platí $I'(x) = d$, pre nejaké $d\in \Dom$.
\end{definition}

Teraz už môžeme formálne zadefinovať, kedy je formula v danej štruktúre
splnená (niekedy hovoríme tiež \emph{platná}).

\begin{definition}
\textbf{Splnená formula}\\

Formula $\Pi$ je \emph{splnená}\ v štruktúre $\D = (\Dom,I)$
(označujeme $\D \models \Pi$) ak v závislosti od jej tvaru platí:\\
{\small
\begin{description}
\item[Ak $\Pi=p(t_1, \dots, t_n)$ tak:]
$\D \models p(t_1, \dots, t_n)$ ak $(t_1^I, \dots, t_n^I) \in
p^I$;
\item[Ak $\Pi=\neg \Phi$ tak:]
$\D \models \neg \Phi$ ak $\D \not\models \Phi$;
\item[Ak $\Pi=\Phi \land \Psi$ tak:]
$\D \models (\Phi \land \Psi)$ ak $\D \models \Phi$ a
$\D \models \Psi$;
\item[if $\Phi \lor \Psi$ tak:]
$\D \models (\Phi \lor \Psi)$ ak $\D \models \Phi$ alebo
$\D \models \Psi$;
\item[Ak $\Pi=\Phi \rightarrow \Psi$ tak:]
$\D \models (\Phi \rightarrow \Psi)$ ak $\D \not\models
\Phi$ alebo $\D \models \Psi$;
\item[Ak $\Pi=\Phi \leftrightarrow \Psi$ tak:]
$\D \models (\Phi \leftrightarrow \Psi)$ ak $\D \models
\Phi$ práve vtedy, keď $\D \models \Psi$;
\item[Ak $\Pi=(\exists x) \Phi$ tak:]
$\D \models (\exists x) \Phi$ ak $\mathcal{D'} \models \Phi$ pre
ľubovoľné rozšírenie\ $\D'$ štruktúry $\D$ vzhľadom na $x$;
\item[Ak $\Pi=(\forall x) \Phi$ tak:]
$\D \models (\forall x) \Phi$ ak $\mathcal{D'} \models \Phi$ pre
všetky rozšírenia $\D'$ štruktúry $\D$ vzhľadom na $x$;
\end{description}
}
kde $\Phi,\Psi$ sú formuly a $p(t_1, \dots, t_n)$ je uzavretý atóm.
\end{definition}

Teraz si povieme niečo o modeloch. Model si môžeme predstaviť ako náš
vlastný model sveta, ktorý si vymyslíme a budeme chcieť, aby v ňom daná
teória platila. Už sme si predstavili pojem štruktúry, a vieme, že
štruktúry slúžia na overovanie platnosti formúl. Takú štruktúru, v ktorej
sú splnené všetky formuly danej teórie budeme nazývať modelom tejto teórie.
Model je teda taký popis sveta, v ktorom daná teória platí.

\begin{definition}
\textbf{Model}

Štruktúra $\D$ je \emph{model} $\Phi$ ak $\D\models\Phi$;
$\D$ je modelom teórie $T$ (označované $\D\models T$)
ak $\D\models\Phi$ pre všetky $\Phi\in T$.
\end{definition}

Tu sa dostávame ku základnej otázke, na ktorú veľmi často narazíme a to, či
môže vôbec nejaká skúmaná formula platiť -- či dáva zmysel. Za zmysluplné
budeme považovať len takú formulu, pre ktorú existuje aspoň jedena
štruktúra, v ktorej je táto formula splnená. Teda, formula má aspoň jeden
model. Takýmto formulám budeme hovoriť splniteľné formuly. A podobne pre
celé teórie.

\begin{definition}
\textbf{Splniteľnosť}

Formula $\Phi$ (alebo teória $T$) je \emph{splniteľná}, ak existuje
štruktúra $\D$ taká, že $\D\models\Phi$ (respektíve  $\D\models T$).
\end{definition}

Ďalším dôležitým pojmom je pojem \emph{vyplývania}.  O explicitných a
implicitných znalostiach sme si hovorili na začiatku.  Vyplývanie je to
kľúčový pojem pre formalizáciu vyvodenia implicitných znalostí z tých,
ktoré sú explicitne uložené v báze znalostí. Toto pravidlo nám umožňuje
správne a ekvivalentne pracovať s výrazmi a ich sémantikou.  Ak modely
chápeme ako všetky svety, v ktorých daná teória platí, tak potom prijmeme
aj všetky tie formule, ktoré sú vo všetkých týchto svetoch tiež vždy
splnené, čiže musia v každom takom svete nutne platiť. Inak povedané, vždy
keď daná teória platí, musí platiť aj daná formula, teda táto formula z
teórie vyplýva. 

\begin{definition}
\textbf{Vyplývanie}

Formula $\Phi$ \emph{vyplýva} z teórie $T$ (označujeme $T \models \Phi$)
ak pre každý model $\D$ teórie $T$ platí $\D\models\Phi$.
\end{definition}

Nadviažeme na príklad spomínaný vyššie a hovorí o tom, že Jack zabil Johna.
A platí, že keď niekto niekoho zabije, tak je to vrah a vrahovia idú do
väzenia. Z toho nám vyplýva, že Jack pôjde do väzenia. A skutočne, pre teóriu
$T$, ktorú sme na formalizáciu tejto situácie zostavili vyššie platí
$T\models\mathit{Väzenie(Jack)}$. Mohli by sme to formálne dokázať
napríklad tak, že by sme vypísali všetky modely teórie $T$ a overili, či v
nich je splnená aj formula $\mathit{Väzenie(Jack)}$. To by ale bolo pomerne
zdĺhavé.

\subsection{Dôkaz}

Uvedomme si teda, že sémantika a modely nám síce určujú, kedy formula z
teórie vyplýva, nenapovedajú nám ale, ako máme takéto formuly
získať, vypočítať. Na to slúži kalkul alebo tiež \emph{dôkaz}. Ponúka nám
systém, ktorým manipulujeme so symbolmi, s formulami, teda na úrovni
syntaxe. Môžeme tak vyvodiť platné formuly (implicitné poznatky).

Formula $(P \land ( P \rightarrow Q )) \rightarrow Q$ je tautológia, to znamená, že je 
vždy splnená v každej štruktúre. Je teda nezávislá od interpretácie.
Intuitívne táto formula hovorí, že ak formuly $P$ aj $P \rightarrow Q$ platia, tak musí platiť aj formula $Q$. Tým pádom pre ľubovolnú teóriu $T$: ak $T \models P$ a $T \models P
\rightarrow Q$ môžeme usúdiť $T \models Q$. Vyjadríme to s
\emph{odvodzovacím pravidlom} zvaným tiež \emph{Modus Ponens}:

$$\frac{P, P \rightarrow Q}{Q}$$

A práve \emph{kalkul} je taký systém, ktorý nám umožňuje odvodzovať formuly
pomocou odvodzovacích pravidiel. Odvodenie formuly $\Phi$ z $T$ sa nazýva a
\emph{dôkaz} $\Phi$ z $T$.  Označujeme $T \vdash \phi$ ak formula $\Phi$ je
odvodená z $T$ za pomoci kalkulu.

Pri odvodzovaní dôkazov budeme potrebovať operáciu dosadenia termu za
premennú. Táto operácia sa nazýva substitúcia.

\begin{definition}
\textbf{Substitúcia}

Formula $\Psi$ vznikne z formuly $\Phi$ \emph{substitúciou premennej 
$x$ termom $t$} (označujeme $\Psi=\Phi\{x/t\}$), ak je totožná s formulou $\Phi$
s výnimkou, že každý výskyt premennej $x$ je nahradený termom $t$.
\end{definition}

Hovoríme tiež, že term $t$ je \emph{substituovateľný} za premennú $x$ vo
formule $\Phi$, ak sa po tejto substitúcii žiadny výskyt premennej v $t$ sa
nestane nestane viazaný kvantifikátorom. Výskyt premennej je viazaný
kvantifikátorom, aj sa nachádza v jeho rozsahu.

Zadefinujeme si teraz Hilbertov kalkul, dokazovací systém, ktorý zostavil
Hilbert \cite{hilbert}.

\begin{definition}
\textbf{Hilbertov kalkul}

Hilbertov kalkul pozostáva z nasledovných axióm:
\begin{align*}
& (P \rightarrow (Q \rightarrow P))
  && \text{(A1)}\\[1.2ex]
& ((P \rightarrow (Q \rightarrow R)) \rightarrow ((P \rightarrow Q) \rightarrow (P \rightarrow R)))
  && \text{(A2)}\\[1.2ex]
& ((\neg P \rightarrow \neg Q) \rightarrow (Q \rightarrow P))
  && \text{(A3)}\\[1.2ex]
& ((\forall x) P \rightarrow P\{x/t\})
\text{, kde term t je substituovateľný za $x$ v $P$}
  && \text{(A4)}\\[1.2ex]
& ((\forall x)(P \rightarrow Q) \rightarrow (P \rightarrow (\forall x)Q))
  && \text{(A5)}
\end{align*}
ako aj z dvoch inferenčných pravidiel:
\begin{itemize}
\item Modus Ponens (MP):
$$\frac{P, (P \rightarrow Q)}{Q}$$
\item Generalizácia (G):
$$\frac{P}{(\forall x) P}$$
\end{itemize}
\end{definition}

Axiómy A1 -- A5 sú v skutočnosti takzvané axiómové schémy, pre ktoré platí,
že ich môžeme inštancovať ľubovolnými formulami $P$ a $Q$. To znamená, že
tieto schémy nám dávajú len návod na to ako v praxi postupovať pri
dokazovaní skúmaných vecí. Za formule $P$ a $Q$ si teda môžeme doplniť
ľubovolné iné formule (často omnoho zložitejšie).

Teraz si zadefinujeme dôkaz v Hilbertovom kalkule a ukážeme si ako
postupovať pri dokazovaní želaných formúl. V praxi sa stretneme veľakrát s
prípadmi, kedy si ,,v hlave'' jednoducho vieme odvodiť, že to tak má byť, ale
formálne to bude trošku zložitejšie. 

\begin{definition}
Dôkaz $\Phi$ z $T$ v Hilbertovom kalkule je postupnosť $\langle
\Phi_1, \Phi_2, \dots, \Phi_n\rangle$ taká, že $\Phi_n = \Phi$ a pre všetky
$1\leq i \leq n$ platí jedna z nasledujúcich možností:
\begin{enumerate}
\item $\Phi_i$ je inštanciou axiómu;
\item $\Phi_i \in T$;
\item $\Phi_i$ je odvodená z formúl $\Phi_1,\dots,\Phi_{i-1}$ jedným z
odvodzovacích pravidiel.
\end{enumerate}
\end{definition}

Dve dôležité vlastnosti, ktoré každý kalkul môže mať, ale aj nemusí ich
mať, sú \emph{zdravosť} a \emph {úplnosť}. Tieto vlastnosti určujú, či je
kalkul korektný (ak ich spĺňa), respektíve do akej miery je korektný (ak
spĺňa len jednu z nich).

Zdravosť kalkulu nám zaručuje, že ním nikdy neodvodíme nezmysel, a teda
formulu, ktorá z danej teórie v skutočnosti nevyplýva.  Inak povedané -- ak
nejakú formulu vieme dokázať, tak táto formula naozaj vyplýva z danej
teórie.

\begin{definition}\label{def:zdravost}
\textbf{Zdravosť}

Kalkul je \emph{zdravý}, ak pre všetky teórie $T$ a pre všetky formuly
$\Phi$, $T\vdash\Phi$ implikuje $T\models\Phi$.
\end{definition}

Úplnosť kalkulu nám naopak zaručuje, že ním vieme dokázať všetky formuly,
ktoré z danej teórie vyplývajú. Hovorí nám teda o tom, že keď si zoberieme
ľubovolnú formulu, ktorá z danej teórie vyplýva, tak je táto formula aj
dokázateľná z danej teórie za pomoci kalkulu.

\begin{definition}\label{def:uplnost}
\textbf{Úplnosť}

Kalkul je \emph{úplný}, ak pre všetky teórie $T$ a pre všetky formuly
$\Phi$, $T\models\Phi$ implikuje $T\vdash\Phi$.
\end{definition}

Vráťme sa opäť k príkladu s Jackom a s Johnom. Uvažovali sme nasledovnú
teóriu $T$, v ktorej si jednotlivé formule označíme:

\begin{align*}
& \mathit{Zabil(Jack,John)}
  && \text{(T1)} \\
& \mathit{(\forall x)((\exists y) Zabil(x,y) \rightarrow Vrah(x))} 
  && \text{(T2)}\\
& \mathit{(\forall x) (Vrah(x) \rightarrow Väzenie(x))}
  && \text{(T3)}\\
\end{align*}

Vyššie sme sa dozvedeli, že $T\models\mathit{Väzenie}(Jack)$, teda, že z
teórie $T$ podľa sémantiky vyplýva tvrdenie, ktoré môžeme interpretovať ako
,,Jack pôjde do väzenia''. Ukážeme si teraz, ako to formálne dokážeme za
pomoci Hilbertovho kalkulu:

\begin{align*}
\text{(1)}\ \ & \mathit{(\forall Y) \neg Zabil(Jack,Y) \rightarrow \neg Zabil(Jack,John)}
  && \text{(A4)}\\
\text{(2)}\ \ & \mathit{[(\forall Y)  \neg Zabil(Jack,Y) \rightarrow \neg
Zabil(Jack,John)] }
  && \\
           & \qquad\qquad \mathit{\rightarrow [Zabil(Jack,John) \rightarrow (\exists Y) Zabil(Jack,Y)]}
  && \text{(A3)}\\
\text{(3)}\ \  & \mathit{Zabil(Jack,John) \rightarrow (\exists Y) Zabil(Jack,Y)}
  && \text{(MP(1, 2))}\\
\text{(4)}\ \  & \mathit{(\exists Y) Zabil(Jack,Y)}
  && \text{(MP(T1, 3))}\\
\text{(5)}\ \  & \mathit{(\forall X) [( \exists Y) Zabil(X,Y) \rightarrow
Vrah(X)] }
  && \\
           & \qquad\qquad \mathit{ \rightarrow [(\exists Y) Zabil(Jack,Y) \rightarrow Vrah(Jack)]}
  && \text{(A4)}\\
\text{(6)}\ \  & \mathit{(\exists Y) Zabil(Jack,Y) \rightarrow Vrah(Jack)}
  && \text{(MP(T2, 5))}\\
\text{(7)}\ \  & \mathit{Vrah(Jack)}
  && \text{(MP(4, 6))}\\
\text{(8)}\ \  & \mathit{(\forall x) [ Vrah(X) \rightarrow Väzenie(X)] }
  && \\
           & \mathit{ \qquad\qquad \rightarrow [Vrah(Jack) \rightarrow Väzenie(Jack)]}
  && \text{(A4)}\\
\text{(9)}\ \  & \mathit{Vrah(Jack) \rightarrow Väzenie(Jack)}
  && \text{(MP(T3, 8))}\\
\text{(10)}\ \  & \mathit{Väzenie(Jack)}
  && \text{(MP(7, 9))}\\
\end{align*}

Žiaľ ani zdravosť a úplnosť nášho kalkulu nám vo všeobecnosti nezaručí,
že pre ľubovoľnú formulu budeme vedieť vypočítať, či z danej teórie
vyplýva, alebo nie. Ak si totiž opätovne a lepšie prečítame tieto
vlastnosti, všimneme si, že hovoria iba formulách, ktoré z teórie
vyplývajú. Ak nám teda niekto dá formulu $\Phi$, ktorá z teórie v
skutočnosti nevyplýva, stane sa akurát to, že nebudeme vedieť nájsť jej
dôkaz. Kedy však už vieme, že môžeme prestať dokazovať? To je práve ten
problém -- vo všeobecnosti to nevieme, môžeme dokazovať aj do nekonečna,
pretože problém vyplývania pre prvorádovú logiku je v skutočnosti
nerozhodnuteľný.

Preto sa v ďalších častiach materiálu budeme zaoberať aj jednoduchšími
(slabšími) jazykmi ako je FOL, ktoré sú rozhodnuteľné, ale tiež rôznymi
aproximatívnymi metódami vyvodzovania.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Deskripčná logika}
\label{sec:dl}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\renewcommand{\Dom}{\Delta^\I}

Deskripčná logika slúži na formálny popis konceptov v nejakej doméne a ich
vzťahov, popisuje ich hierarchiu. Pomocou nej vieme definovať pojmy, napr.
pojem zachytávajúci skupinu ľudí pracujúcich v odvetví strojárskeho
priemyslu. Deskripčná logika je fragmentom logiky prvého rádu. Jej
expresívna sila je nižšia, ale výhodou je, že vyplývanie je rozhodnuteľné.
Preto pre každú formulu vieme určiť, či z bázy znalosti vyplýva, alebo nie.
Takéto formálne systémy sú oveľa vhodnejšie na implementáciu.

\subsection{Syntax}


V tejto časti sa zoznámime so syntaxou jazyka $\ALC$, ktorý je jedným z
rodiny deskripčných logík. Viac detailov čitateľ nájde v \cite{dlhb}. Jazyk deskripčnej logiky je vybudovaný nad
slovníkom symbolov.

\begin{definition} 
\textbf{Slovník}

Slovník pozostáva z troch navzájom disjunktných spočítateľných množín:
\begin{enumerate}
	\item Množina individuálov $N_I = \{a, b, \dotsc\}$
	\item Množina atomických konceptov $N_C = \{A, B, \dotsc\}$
	%prvkami sú množiny indivíduí
	\item Množina rolí $N_R = \{R, S, \dotsc\}$
	%binárna relácia vyjadrujúca vzťahy, ak indivíduum \textit{x} je spojené s \textit{y}, tak hovoríme, že \textit{y} je R-nasledovník \textit{x} 
\end{enumerate}
\end{definition}

Pod množinou individuálov si vieme predstaviť objekty nejakej domény,
napríklad konkrétni ľudia, študenti, predmety. Koncepty zasa predstavujú
triedy individuálov. Každý jedno individuál bude patriť do
najvšeobecnejšieho konceptu, ale môže patriť aj do iných konceptov.
$\top $. Napríklad individuál \texttt{jan} môže spadať do konceptu \texttt{Študent} a
s individuálom \texttt{jozef} ho spája rola \texttt{MáSpolužiaka}. Budeme
to vedieť v tejto logike vyjariť.

Koncepty môžme prepájať a vytvárať nové zložené koncepty za pomoci takzvaných
konštruktorov.

\begin{definition}
\subsubsection{Zložené koncepty}
Majme slovník daný množinami $N_I$, $N_C$, a $N_R$. Potom koncepty sú
rekurzívne definované nasledovne:
$$C,D ::= A\ |\ \neg C\ |\ C \sqcap D\ |\ C \sqcup D\ |\ \exists R.C
        \ |\ \forall R.C$$
kde $A\in\NC$, $R\in\NR$, a $C$, $D$ sú koncepty.
\end{definition}

Konštruktory jazyka $\ALC$ nazývame komplement ($\neg$), prienik
($\sqcap$), zjednotenie ($\sqcup)$, existenčné obmedzenie ($\exists$), a
hodnotové obmedzenie ($\forall)$.

Okrem toho si zavedieme špeciálne koncepty $\top$ a $\bot$, prvý bude
predstavovať univerzálny koncept, do ktorého vždy platia všetky
individuály, druhý predstavuje prázdny koncept, do ktorého zasa žiadny
individuál nepatrí. Tieto koncepty si zavedieme len ako jednoduché
syntaktické syntaktické skratky. Nech $A\in N_C$. Potom:

\begin{itemize}
\item $\top = A \sqcup \neg A$\,,
\item $\bot = A \sqcap \neg A$\,.
\end{itemize}

Zo sémantiky (nižšie) bude zrejmé, že dané podmienky sú pre tieto koncepty
splnené.

Podobne ako v prípade FOL, popis nejakej domény, stavu sveta, a podobne,
uložíme do teórie, alebo tiež bázy znalostí. V báze znalostí v DL budeme
reprezentovať vzťahy medzi konceptami, príslušnosť objektu do konceptu a 
priradenie objektu k inému objektu za pomoci rolí. Báza znalostí sa skladá
z dvoch častí.

\begin{description}
	\item[T-Box]  \hfill \\ 
	Prvá časť bázy znalostí (z angl. Terminology Box), ktorá určuje vzťahy medzi konceptami.
	Obsahuje subsumčné axióm tvaru: \begin{gather*}\phi ::= C \isa D,\end{gather*} pričom $C$, $D$ sú koncepty.	
	\item[A-Box]  \hfill \\ 
	Druhá časť bázy znalostí (z angl. Assertion Box) je množina aserčných axióm tvaru: \begin{gather*}\phi ::= a:C\ |\ a,b : R,\end{gather*} kde $a,b\in \NI$, $R\in\NR$, a $C$ je koncept.
\end{description}


\begin{definition}
\textbf{Báza znalostí}

Majme slovník daný množinami $N_I$, $N_C$, a $N_R$. Báza znalostí (KB)
deskripčnej logiky je dvojica $\K = (\T,\A)$ (TBox a ABox), pričom $\T$ je
konečná množina subsumčných axióm a $\A$ je konečná množina aserčných
axióm.
\end{definition}


\subsection{Sémantika}
Podobne ako u FOL, v sémantike DL sa zaoberáme množinou možných svetov, v
ktorých môže báza znalostí platiť. Všetky možné svety predstavujú
interpretácie danej bázy znalostí.

\begin{definition}
\textbf{Interpretácia}
\emph{Interpretácia} danej DL KB $\K=(\T,\A)$ je definovaná ako dvojica $\I =
(\Dom,\cdot^\I)$ pozostávajúca z častí:
\begin{itemize}
\item
doména - množina všetkých dovolených indivíduí ($\Dom\neq\emptyset$\ ),
\item interpretačná funkcia ($\cdot^\I$):\\
      $a^\I \in \Dom$ - pre všetky $a\in\NI$\,\\
      $A^\I \subseteq \Dom$ - pre všetky $A\in\NC$\,\\
      $R^\I \subseteq \Dom\times\Dom$ - pre všetky $R\in\NR$\,\\ \\
\end{itemize}
pričom interpretácia zložených konceptov - je pre dané $C$, $D$ a $R$ definovaná rekurzívne:
\begin{itemize}
\item
      $\neg C^\I = \Dom \setminus C^\I$
\item
      $C \sqcap D^\I = C^\I \cap D^\I$
\item
      $C \sqcup D^\I = C^\I \cup D^\I$
\item
      $\exists R. C^\I = \{x\in\Dom \mid
        \exists y\in\Dom: \Pair{x}{y}\in R^\I \land y\in C^\I\}$
\item
      $\forall R. C^\I = \{x\in\Dom \mid
        \forall y\in\Dom: \Pair{x}{y}\in R^\I \implies y\in C^\I\}$
\end{itemize}
\end{definition}

Ak axióma v danej interpretácii platí, hovoríme, že je v nej splnená, alebo
platná.

\begin{definition}
\subsubsection{Splnené axiómy}

Hovoríme, že axióma $\phi$ je splnená v danej interpretácii $\I =
(\Dom,\cdot^\I)$ (označenie $\I\models\phi$), podľa typu axiómy $\phi$ nasledovne:
\begin{description}
\item[$C \isa D$:] $\I \models C \isa D$ práve vtedy, ak $C^\I \subseteq D^\I$
\item[$a:C$:]      $\I \models a:C$ práve vtedy, ak $a^\I \in C^\I$
\item[$a,b:R$:]      $\I \models a,b:R$ práve vtedy, ak $\Pair{a^\I}{b^\I} \in R^\I$
\end{description}
\end{definition}

\subsubsection{Model}

Tie interpretácie, ktoré spĺňajú všetky axiómy v báze znalostí nazývame jej
modelmi. Modelov môže byť viacero, teda môžeme mať viacero interpretácií,
ktoré sú modelmi. 

\begin{definition}
\subsubsection{Model}
Majme bázu znalostí $\K=(\T,\A)$. Interpretácia $\I = \Pair{\Dom}{\cdot^\I}$ je
modelom $\K$ (označenie $\I\models\phi$), ak $\I$ spĺňa všetky axiómy
patriace do $\T$ a $\A$.
\end{definition}

\subsection{Rozhodovacie problémy}

Úlohou deskripčnej logiky nie je len reprezentovať a uchovávať dáta v nejakej hierarchickej štruktúre poprepájanej všelijakými vzťahmi medzi konceptmi, či indivíduami, ale taktiež sa jej môžme pýtať rôzne typy otázok. Tieto otázky môžu byť dotazy podobné tým databázovým - či sa v našej reprezentácii nachádza indivíduum daného typu, alebo či je relácia medzi indíviduami, ale aj otázky typu, či je tento koncept podmnožinou druhého a pod.
 

Aby boli odpovede na otázky, ktoré kladieme báze znalostí reprezentovanej v deskripčnej logike správne, musíme vedieť overiť konzistenciu bázy znalostí. Treba overiť, či si nejaké axiómy navzájom neodporujú.

\begin{definition}
\textbf{Konzistencia bázy znalostí}

Báza znalostí $\K = (\T,\A)$ je $\emph{konzistentná} $ práve vtedy, ak má aspoň jeden \textit{model}.
\end{definition}

Okrem konzistencie bázy znalostí nás zaujíma, či je koncept v danej báze
znalostí splniteľný, teda, či môže mať aspoň jednu inštanciu.

\begin{definition}
\textbf{Splniteľnosť}

Hovoríme, že koncept
$C$ je splniteľný v danej báze znalostí $\K$, ak existuje aspoň 
jeden model $\I$ bázy znalostí $\K$ taký, že množina $C^\I$ je neprázdna.
\end{definition}

Zaujímavou a nesporne užitočnou úlohou je tiež zistiť aké implicitné vzťahy medzi
konceptami môžeme odvodiť z tých axióm, ktoré sú v báze znalostí explicitne
uložené. Základným takýmto vzťahom je vzťah medzi špecifickejším a
všeobecnejším konceptom, teda vzťah subsumcie.

\begin{definition}
\textbf{Vyplývanie (subsumcia)}

Hovoríme, že koncept
$C$ je subsumovaný konceptom $D$ v báze znalostí $\K$ (označenie
\emph{$\K\models C \isa D$}) práve vtedy, keď
$C^\I \subseteq D^\I$ platí pre každú interpretáciu $\I$, ktorá je modelom
$\K$.
\end{definition}

Splniteľnosť a subsumcia sú vzájomne redukovateľné: platí, že $\K\models
C\isa D$ práve vtedy, keď $C\sqcap \neg D$ je nesplniteľné v $\K$; a naopak
$C$ je splniteľné v $\K$ práve vtedy, keď $\K\not\models C\isa\bot$. Ciže
v praxi nám stačí zaoberať sa jednou z týchto úloh, najčastejšie je to
splniteľnosť. Stačí nám tiež konzistentnosť KB, pretože splniteľnosť $C$ v
$\K$ vieme
overiť aj tak, že do $\K$ pridáme novú axiómu $a:C$, kde $a$ je nejaký nový
individuál, ktorý sa v $\K$ inde nevyskytuje, a overíme, či je
konzistentná \cite{dlhb}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Maticový počet}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Úvod}

V praxi sa často stretneme s pojmom matica a maticový počet. Maticový počet
sa využíva vo veľmi širokom spektre uplatnení.  Je preto potrebné, aby sme
sa oboznámili s jeho základnými pojmami a funkciami. Viac informácií možno
nájsť v \cite{algebra}.

Maticu si môžeme predstaviť ako tabuľku s číslami, s ktorými vieme pracovať
a robiť rôzne operácie. S maticami pracujeme a využívame ich na riešenie veľa
potrebných a užitočných vecí. Veľakrát sa v praxi stretnete s problémami,
ktoré sa nebudú dať len tak jednoducho riešiť a práve matice nám v tom
veľmi efektívne budú vedieť pomôcť.

Zadefinujeme si maticu a následne si ukážeme základne operácie s maticami, ktoré poznáme. 

\begin{definition}
\textbf{Matica}

Nech \emph{X} je ľubovoľná množina a \emph{$m, n \in N$}. Maticou
typu \emph{$m \times n$}, alebo tiež \emph{$m \times n$}-rozmernou maticou
nad množinou X rozumieme obdĺžnikovú tabuľku pozostávajúcu z prvkov množiny
$X$. Pre matice používame nasledovnú notáciu:

\begin{equation*}
\mathbf{A}_{m,n} = \left(
\begin{array}{cccc}
a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\
\vdots  & \vdots  & \ddots & \vdots \\
a_{m,1} & a_{m,2} & \cdots & a_{m,n} \\
\end{array} \right)
\end{equation*}

\end{definition}

Uvedieme si teraz niekoľko definícií a vlastnosti matíc, ktoré je potrebné si osvojiť.

\begin{definition}
\textbf{Diagonála matice}

Majme štvorcovú maticu \emph{$A$}. Potom prvky matice $a_{i,j}$, pre ktoré platí $i = j$, tvoria hlavnú diagonálu matice.
\end{definition}

\begin{definition}
\textbf{Vedľajšia diagonála matice}

Majme štvorcovú maticu\emph{$A$}. Potom prvky matice $a_{i,j}$, pre ktoré platí $j = n-i+1$ tvoria vedľajšiu diagonálu matice.
\end{definition}
 
Základné vlastnosti:

\begin{itemize}
\item
Prvky $a_{i,j} \in X$, kde $1 \le i \le m, 1 \le j \le n$, sa nazývajú
prvkami matice. Číslo \emph{m} reprezentuje počet riadkov matice \emph{$A$} a
\emph{n} reprezentuje počet stĺpcov matice \emph{$A$}. Prvok $a_{i,j}$ nachádzajúci sa v \emph{i}-tom riadku a \emph{j}-tom stĺpci matice nazývame tiež prvok v mieste \emph{$(i, j)$}, prípadne $(i, j)$-ty prvok matice. 
\item
Ak $a_{i, j} = 0$ pre $(\forall i) i = 1 \ldots m,  j = 1 \ldots n$  nazývame nulovou maticou 

\begin{equation*}
\mathbf{X} = \left(
\begin{array}{cccc}
0 & 0 &\cdots & 0 \\ 
0 & 0 &\cdots & 0 \\
\vdots  & \vdots  & \ddots & \vdots \\
0 & 0 & \cdots & 0 \\
\end{array} \right)
\end{equation*}

\item
Ak počet riadkov je rovný počtu stĺpcov ($m = n$)  nazývame danú maticu $\emph{A}_{m,n}$ štvorcová matica rádu $n$
\item
Štvorcová matica rádu $n$, ktorá má na hlavnej diagonále samé $1$ a ostatné prvky sú nulové sa nazýva jednotková matica

\begin{equation*}
\mathbf{X} = \left(
\begin{array}{cccc}
1 & 0 & \cdots & 0 \\ 
0 & 1 & \ddots & 0 \\ 
\vdots & \ddots & \ddots & \vdots \\ 
0 & \cdots & 0 & 1 
\end{array} \right)
\end{equation*}

\item
Štvorcová matica rádu $n$, ktorá má mimo hlavnej diagonály všetky prvky
nulové sa nazýva diagonálna matica
\item
Nech matica $\emph{A}_{m,n}$ je matica typu $m \times n$ a zároveň platí, že $a_{i,j} = b_{j,i}$ pre $1 \le i \le m, 1 \le j \le n$. Potom maticu $\emph{B}_{n,m }$ typu $n \times m$ nazývame transponovanou maticou ku matici A.
Označujeme $\textbf{B}^{T} = \textbf{A}$

Voľne povedané, riadky pôvodnej matice sa stávajú stĺpcami v transponovanej matici (a naopak).
\end{itemize}

\subsection{Operácie s maticami}

S maticami ako objektami môžeme narábať podobne ako s číslami. Matica
vlastne nie je nič iné ako tabuľka čísiel a tým pádom tam budú platiť
podobné princípy a pravidlá ako s číslami. 

Nebudeme sa zaoberať všeobecnými pravidlami a zákonitosťami aké poznáme pri
práci s číslami, ale uvedieme si len pár potrebných, ktoré sa nám neskôr zídu.

K základným algebraickým operáciám s maticami patria vynásobenie matice konštantou, súčet matíc a súčin matíc. 

Operácia súčet bude fungovať tak ako by si človek pri prvej predstave
pomyslel. Budeme sčitovať jednotlivé prvky matice na rovnakej pozícií,
preto je aj potrebné, aby matice mali rovnaký rozmer. 

\begin{definition}
\textbf{Sčítanie dvoch matíc}

Majme maticu $\emph{A}_{m,n}$ s prvkami $a_{i,j}$ a maticu $\emph{B}_{m,n}$ s prvkami $b_{i,j}$. Maticu $\emph{C}_{m,n}$ typu $m \times n$ nazývame súčtom matíc \emph{$A$} a \emph{$B$} a píšeme $\emph{C} = \emph{A} + \emph{B}$ ak platí $c_{i,j} = a_{i,j} + b_{i,j}$ pre všetky $i =  1 , 2 , \ldots, m$ a $k = 1 , 2 , \ldots , n$. 
\end{definition}

Uvedieme si príklad :
 
\begin{equation*}
\mathbf{A} = \left(
\begin{array}{ccc}
 1 & 2 & 4 \\
 7 & 6 & 3 \\
 -3 & 0 & 2 \\
\end{array} \right)
\end{equation*}

\begin{equation*}
\mathbf{B} = \left(
\begin{array}{ccc}
  1 & 8 & 3 \\
  2 & 4 & 2 \\
  3 & 6 & 1 \\
\end{array} \right)
\end{equation*}

Matica \emph{$C$} potom bude vyzerať nasledovne:

\begin{equation*}
\mathbf{C} = \left(
\begin{array}{ccc}
  2 & 10 & 7 \\
  9 & 10 & 5 \\
  0 & 6 & 3 \\
\end{array} \right)
\end{equation*}


Čo sa týka násobenia matice konštantou funguje to obdobne. Každý prvok násobenej matice vynásobíme daným číslom.

\begin{definition}
\textbf{Násobenie matice konštantou}

Ak $\emph{A}_{m,n}$ s prvkami $a_{i,j}$ je matica a $d$ je konštanta, tak
$d$-násobok matice \emph{$A$} je matica \emph{$dA$} typu $m \times n$ kde prvkami sú  $d\cdot a_{i,j}$
\end{definition}

Uvedieme si príklad: Nech
 
\begin{equation*}
\mathbf{A} = \left(
\begin{array}{ccc}
 1 & 2 & 4 \\
 7 & 6 & 3 \\
-3 & 0 & 2 \\
\end{array} \right)
\end{equation*}

a konštanta $d = 3$. Znak násobenia sa väčšinou vynecháva a píšeme iba \emph{$dA$} .Matica \emph{$dA$} teda potom bude vyzerať nasledovne:

\begin{equation*}
\mathbf{dA} = \left(
\begin{array}{ccc}
 3 & 6 & 12 \\
 21 & 18 & 9 \\
 -9 & 0 & 6 \\
\end{array} \right)
\end{equation*}

Ako poslednú a zároveň jednu z tých ťažších operácií si uvedieme operáciu
násobenia dvoch matíc. Tu sa stretávame s problémom a to tým, že to nie je
také jednoduché ako by si to možno človek predstavoval. Keď budeme násobiť
dve matice neplatí tam pravidlo, že budeme násobiť každý prvok s každým,
alebo prvky na rovnakých pozíciách.

Násobenie matíc je o to zložitejšie, že budeme násobiť prvky jedného riadku
matice s prvkami jedného stĺpca matice. Maticu \emph{$A$} preto možno
(sprava) vynásobiť maticou \emph{$B$} len vtedy, ak počet stĺpcov matice \emph{$A$} sa rovná počtu riadkov matice \emph{$B$}.

\begin{definition}
\textbf{Násobenie dvoch matíc}

Ak $\emph{A}_{m,n}$ s prvkami $a_{i,j}$ a $\emph{B}_{n,l}$ s prvkami $b_{i,j}$ sú matice typu $m \times n$ a typu $n \times l$, potom ich súčinom je matica $ \emph{C} = \emph{A.B} $ typu $m \times l$, ktorej $(i,j)$-ty prvok vypočítame pomocou vzťahu
\end{definition}

$$ c_{i,j} = a_{i,1}b_{1,j} + a_{i,2}b_{2,j} + \ldots + a_{i,n}b_{n,j} $$

Uvedieme si príklad :
 
\begin{equation*}
\mathbf{A} = \left(
\begin{array}{ccc}
 1 & 2 & 3 \\
 2 & 6 & 1 \\
 0 & 3 & 2 \\
\end{array} \right)
\end{equation*} 

\begin{equation*}
\mathbf{B} = \left(
\begin{array}{ccc}
 1 & 4 & 3 \\
 2 & 3 & 2 \\
 3 & 2 & 1 \\
\end{array} \right)
\end{equation*} 

Matica \emph{C} potom bude vyzerať nasledovne:

\begin{equation*}
\mathbf{C} = \left(
\begin{array}{ccc}
14 & 16 & 10 \\
17 & 28 & 19 \\
12 & 13 & 8 \\
\end{array} \right)
\end{equation*} 

\subsection{Numerické riešenie sústavy lineárnych rovníc}

Riešenie sústav lineárnych rovníc patrí medzi najdôležitejšie časti numerickej matematiky. Veľa praktických úloh nakoniec vedie k riešeniu takýchto sústav, často veľmi rozsiahlych.  

Množstvo problémov v technických, prírodných a sociálnych vedách vedie ku rovniciam, ktoré
obsahujú dve triedy premenných. Rovnica typu

$$ y = ax $$

vyjadrujúca závislú premennú $y$ pomocou nezávislej premennej $x$ a
konštanty $a$, sa nazýva lineárna rovnica. Podobne, rovnica

$$ a_1x_1 + a_2x_2 + \ldots + a_nx_n = b $$

ktorá vyjadruje b pomocou premenných $x_1, x_2, \ldots , x_n$ a známych
konštánt $a_1, a_2, \ldots , a_n$
je rovnicou lineárnych rovníc. V mnohých prípadoch a aplikáciách však bývajú dané konštanty
$b, a_1, a_2, \ldots , a_n$ a naopak musíme nájsť čísla $x_1, x_2, \ldots, x_n$, ktoré danú rovnicu
spĺňajú.

Budeme sa zaoberať riešením sústav $n$ lineárnych rovníc:

\begin{gather*}
 a_{11}x1  +  a_{12}x2 + \ldots + a_{1n}xn  =   b_1\\
 a_{21}x1  +  a_{22}x2 + \ldots + a_{2n}xn  =   b_2\\ 
 \vdots\\
 a_{n1}x1  +  a_{n2}x2 + \ldots + a_{nn}xn  =   b_n
\end{gather*}
s $n$ neznámymi $x_1, x_2, \ldots , x_n$.  

Danú sústavu môžeme zapísať v maticovom tvare 
  
$$A . x = b  $$ 

kde  

\begin{equation*}
\mathbf{A} = \left(
\begin{array}{cccc}
 a_{11} & a_{12} & \ldots & a_{1n} \\
 a_{21} & a_{22} & \ldots & a_{2n} \\
 \vdots & \vdots & \ddots & \vdots \\
 a_{n1} & a_{n2} & \ldots & a_{nn} 
\end{array} \right)
\end{equation*} 

\begin{equation*}
\mathbf{x} = \left(
\begin{array}{c}
 x_1 \\
 x_2 \\
 \vdots \\
 x_n \\
\end{array} \right)
\end{equation*} 

\begin{equation*}
\mathbf{b} = \left(
\begin{array}{c}
 b_1 \\
 b_2 \\
 \vdots \\
 b_n \\
\end{array} \right)
\end{equation*} 

Matica \emph{$A$} s prvkami $a_{i,j}, i,j = 1,\ldots, n$ , sa nazýva matica
sústavy, stĺpcový vektor $b = (b_1, b_2, \ldots, b_n)$ vektor pravých strán
a vektor $x = ( x_1,x_2, \ldots ,x_n)$ je vektor neznámych.  

Aby sme vedeli riešiť sústavu n lineárnych rovníc, ale aj hocijakú inú sústavu rovníc, potrebujeme si uvedomiť, čo je riešením, aké úpravy a metódy môžeme využívať pri hľadaní riešenia a kedy riešenie existuje a kedy naopak nie. 

\begin{definition}
\textbf{Riešenie lineárnych rovníc}

Pod riešením sústavy rozumieme usporiadanú n-ticu $(r_1, r_2, \ldots , r_n)$, kde keď dosadíme $r_j$ za $x_j$ do všetkých rovníc dané rovnice budú identické. 

Sústava lineárnych rovníc sa nazýva riešiteľná  (respektíve neriešiteľná), ak existuje (neexistuje) aspoň jedno takéto riešenie.
\end{definition}

Pri riešení teda budeme pracovať s maticami a operáciami nad nimi. Niektoré
operácie sme si už uviedli v predchádzajúcej kapitole, ale je potrebné aby
sme si uviedli aj nasledujúce, ktoré sa nazývajú takzvané ekvivalentné
úpravy matice, aby sme vedeli vyriešiť danú sústavu a našli sme hľadaný
vektor riešení $r$.

\begin{definition}
\textbf{Ekvivalentná úprava}

Dve sústavy nazývame ekvivalentnými, ak množiny ich riešení sú rovnaké.
Akúkoľvek úpravu sústavy lineárnych rovníc, po ktorej bude daná sústava
ekvivalentnou, nazývame ekvivalentná úprava.  \end{definition}

Ekvivalentné úpravy poznáme nasledovné: 

\begin{itemize}
\item
 ľubovolná zmena podaria riadkov rovníc (čiže aj riadkov matice)
\item
 vynásobenie ľubovolnej rovnice nenulovým číslom
\item
 pripočítanie ľubovolnej lineárnej kombinácie ostatných rovníc ku rovnici 
\end{itemize}

Dané úpravy sme si definovali pre rovnice sústavy. Avšak keď si uvedomíme,
že jednotlivé riadky matice reprezentujú jednotlivé rovnice, uvedomíme si,
že dané úpravy môžeme aplikovať až na riadky matice.

Sústava ma práve jedno riešenie práve vtedy keď matica sústavy je regulárna. Ak je matica sústavy singulárnou maticou, sústava rovníc ma v $R$ (reálne čísla) nekonečno veľa riešení alebo žiadne.

Regulárna matica je taká matica, ktorá ma rovnaký počet riadkov a stĺpcov.
Singulárna matica je naopak taká, ktorá ma rôzny počet riadkov a stĺpcov.

Pri riešení takejto sústavy rovníc používame takzvanú rozšírenú maticu sústavy, ktorá sa skladá z matice sústavy a vektora pravých strán. Daná matica teda bude vyzerať nasledovne:

\begin{equation*}
\mathbf{A|b} = \left(
\begin{array}{cccccc}
 a_{11} & a_{12} & \ldots & a_{1n} & | & b_1 \\
 a_{21} & a_{22} & \ldots & a_{2n} & | & b_2\\
 \vdots & \vdots & \ddots & \vdots & | & \vdots \\
 a_{n1} & a_{n2} & \ldots & a_{nn} & | & b_n\\
\end{array} \right)
\end{equation*}

S tou maticou začíname pri hľadaní riešenie a hľadáme ho aplikovaním
ekvivalentných úprav. Daná maticu sa snažíme dostať do podoby takzvanej
hornej trojuholníkovej matice, kedy na diagonále sú samé
$1$ a pod diagonálou sú iba samé $0$.

\begin{equation*}
\mathbf{A'} = \left(
\begin{array}{ccccc}
 1 & -3 & 8 & \ldots & 4 \\
 0 & 1 & 5 & \ldots & 7 \\
 0 & 0 & 1 & \ldots & 7 \\
 \vdots & \vdots & \vdots & \ddots & \vdots \\
 0 & 0 & 0 & \ldots & 1 \\
\end{array} \right)
\end{equation*} 

Riešenie následne nájdeme vyriešením danej upravenej sústavy rovníc.

Na ilustráciu si uvedieme jednoduchý príklad :

V množine reálnych čísel riešte sústavu rovníc

\begin{eqnarray}
  x -  2y + 4z +   t  =  -6 \\
  2x + 3y -   z  + 2t  = 13  \\
  2x + 5y +  z  +   t  =   8  \\
  3x +   y + 3z +   t  =   1 
\end{eqnarray}

Maticový tvar bude teda vyzerať nasledovne :

\begin{equation*}
\mathbf{A} = \left(
\begin{array}{cccc}
1 & -2 & 4 & 1 \\
2 & 3 & -1 & 2 \\
2 & 5 & 1 & 1 \\
3 & 1 & 3 & 1
\end{array} \right)
\end{equation*} 

\begin{equation*}
\mathbf{x} = \left(
\begin{array}{c}
 x \\
 y \\
 z \\
 t \\
\end{array} \right)
\end{equation*} 

\begin{equation*}
\mathbf{b} = \left(
\begin{array}{c}
 -6 \\
 13 \\
 8 \\
 1 \\
\end{array} \right)
\end{equation*} 

Rozšírená matica sústavy:

\begin{equation*}
\mathbf{A|b} = \left(
\begin{array}{cccccc}
1 & -2 & 4 & 1 & | & -6\\
2 & 3 & -1 & 2 & | & 13\\
2 & 5 & 1 & 1 & | & 8\\
3 & 1 & 3 & 1 & | & 1
\end{array} \right)
\end{equation*} 

Následná úprava na trojuholníkový tvar:

\begin{itemize}
\item
 od druhého riadku odpočítame dvojnásobok prvého
\item
 od tretieho riadku odpočítame dvojnásobok prvého
\item
 od štvrtého riadku odpočítame trojnásobok prvého 
\end{itemize}

dostaneme

\begin{equation*}
\left(
\begin{array}{cccccc}
1 & -2 & 4 & 1 & | & -6\\
0 & 7 & -9 & 0 & | & 25\\
0 & 9 & -7 & -1 & | & 10\\
0 & 7 & -9 & -2 & | & 19
\end{array} \right)
\end{equation*} 

\begin{itemize}
\item
 druhý riadok vydelíme siedmymi
\end{itemize}

\begin{equation*}
\left(
\begin{array}{cccccc}
1 & -2 & 4 & 1 & | & -6\\
0 & 1 & -9/7 & 0 & | & 25/7\\
0 & 9 & -7 & -1 & | & 10\\
0 & 7 & -9 & -2 & | & 19
\end{array} \right)
\end{equation*} 

\begin{itemize}
\item
 od tretieho riadku odpočítame deväťnásobok druhého
\item
 od štvrtého riadku odpočítame sedemnásobok druhého 
\end{itemize}

\begin{equation*}
\left(
\begin{array}{cccccc}
1 & -2 & 4 & 1 & | & -6\\
0 & 1 & -9/7 & 0 & | & 25/7\\
0 & 9 & 32/7 & -1 & | & -85/7\\
0 & 7 & 0 & -2 & | & -6
\end{array} \right)
\end{equation*}

\begin{itemize}
\item
  tretí riadok vynásobíme $7$ a vydelíme $32$, štvrtý riadok vydelíme $-2$
\end{itemize}

a dostaneme

\begin{equation*}
\left(
\begin{array}{cccccc}
1 & -2 & 4 & 1 & | & -6\\
0 & 1 & -9/7 & 0 & | & 25/7\\
0 & 9 & 1 & -7/32 & | & -85/32\\
0 & 7 & 0 & 1 & | & 3
\end{array} \right)
\end{equation*}

K danej poslednej matici stačí napísať príslušnú sústavu

\begin{eqnarray*}
  x -  2y + 4z  +   t  =  -6 \\
       y -  9/7z      = 25/7  \\
           z - 7/32t  =   -85/32"  \\
                   t  =   3 
 \end{eqnarray*}

Postupným dosadením výsledku spodnej rovnice do rovníc vyššie, a opakovaním
tohto postupu už dostaneme jednoznačné riešenie:

\begin{eqnarray*}
  x  =  1 \\
  y  =  1  \\
  z  = -2  \\
  t  =  3 
\end{eqnarray*}

